/*
 * Copyright (c) 2007-2012, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
/*
 * Copyright 1999-2004 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * $Id: DTMDefaultBaseTraversers.java,v 1.2.4.1 2005/09/15 08:15:00 suresh_emailid Exp $
 */
package com.sun.org.apache.xml.internal.dtm.ref;

import com.sun.org.apache.xml.internal.dtm.*;

import javax.xml.transform.Source;

import com.sun.org.apache.xml.internal.utils.XMLStringFactory;

import com.sun.org.apache.xml.internal.res.XMLErrorResources;
import com.sun.org.apache.xml.internal.res.XMLMessages;
import com.sun.org.apache.xalan.internal.xsltc.dom.NodeCounter;

/**
 * This class implements the traversers for DTMDefaultBase.
 *
 * PLEASE NOTE that the public interface for all traversers should be
 * in terms of DTM Node Handles... but they may use the internal node
 * identity indices within their logic, for efficiency's sake. Be very
 * careful to avoid confusing these when maintaining this code.
 * */
public abstract class DTMDefaultBaseTraversers extends DTMDefaultBase {

    /**
     * Construct a DTMDefaultBaseTraversers object from a DOM node.
     *
     * @param mgr The DTMManager who owns this DTM.
     * @param source The object that is used to specify the construction source.
     * @param dtmIdentity The DTM identity ID for this DTM.
     * @param whiteSpaceFilter The white space filter for this DTM, which may
     *                         be null.
     * @param xstringfactory The factory to use for creating XMLStrings.
     * @param doIndexing true if the caller considers it worth it to use
     *                   indexing schemes.
     */
    public DTMDefaultBaseTraversers(DTMManager mgr, Source source, int dtmIdentity, DTMWSFilter whiteSpaceFilter, XMLStringFactory xstringfactory, boolean doIndexing) {
        super(mgr, source, dtmIdentity, whiteSpaceFilter, xstringfactory, doIndexing);
    }

    /**
     * Construct a DTMDefaultBaseTraversers object from a DOM node.
     *
     * @param mgr The DTMManager who owns this DTM.
     * @param source The object that is used to specify the construction source.
     * @param dtmIdentity The DTM identity ID for this DTM.
     * @param whiteSpaceFilter The white space filter for this DTM, which may
     *                         be null.
     * @param xstringfactory The factory to use for creating XMLStrings.
     * @param doIndexing true if the caller considers it worth it to use
     *                   indexing schemes.
     * @param blocksize The block size of the DTM.
     * @param usePrevsib true if we want to build the previous sibling node array.
     * @param newNameTable true if we want to use a new ExpandedNameTable for this DTM.
     */
    public DTMDefaultBaseTraversers(DTMManager mgr, Source source, int dtmIdentity, DTMWSFilter whiteSpaceFilter, XMLStringFactory xstringfactory, boolean doIndexing, int blocksize, boolean usePrevsib, boolean newNameTable) {
        super(mgr, source, dtmIdentity, whiteSpaceFilter, xstringfactory, doIndexing, blocksize, usePrevsib, newNameTable);
    }

    /**
     * This returns a stateless "traverser", that can navigate
     * over an XPath axis, though perhaps not in document order.
     *
     * @param axis One of Axes.ANCESTORORSELF, etc.
     *
     * @return A DTMAxisTraverser, or null if the given axis isn't supported.
     */
    public DTMAxisTraverser getAxisTraverser(final int axis) {

        DTMAxisTraverser traverser;

        if (null == m_traversers) // Cache of stateless traversers for this DTM
        {
            m_traversers = new DTMAxisTraverser[Axis.getNamesLength()];
            traverser = null;
        } else {
            traverser = m_traversers[axis]; // Share/reuse existing traverser

            if (traverser != null)
                return traverser;
        }

        switch (axis) // Generate new traverser
        {
            case Axis.ANCESTOR:
                traverser = new AncestorTraverser();
                break;
            case Axis.ANCESTORORSELF:
                traverser = new AncestorOrSelfTraverser();
                break;
            case Axis.ATTRIBUTE:
                traverser = new AttributeTraverser();
                break;
            case Axis.CHILD:
                traverser = new ChildTraverser();
                break;
            case Axis.DESCENDANT:
                traverser = new DescendantTraverser();
                break;
            case Axis.DESCENDANTORSELF:
                traverser = new DescendantOrSelfTraverser();
                break;
            case Axis.FOLLOWING:
                traverser = new FollowingTraverser();
                break;
            case Axis.FOLLOWINGSIBLING:
                traverser = new FollowingSiblingTraverser();
                break;
            case Axis.NAMESPACE:
                traverser = new NamespaceTraverser();
                break;
            case Axis.NAMESPACEDECLS:
                traverser = new NamespaceDeclsTraverser();
                break;
            case Axis.PARENT:
                traverser = new ParentTraverser();
                break;
            case Axis.PRECEDING:
                traverser = new PrecedingTraverser();
                break;
            case Axis.PRECEDINGSIBLING:
                traverser = new PrecedingSiblingTraverser();
                break;
            case Axis.SELF:
                traverser = new SelfTraverser();
                break;
            case Axis.ALL:
                traverser = new AllFromRootTraverser();
                break;
            case Axis.ALLFROMNODE:
                traverser = new AllFromNodeTraverser();
                break;
            case Axis.PRECEDINGANDANCESTOR:
                traverser = new PrecedingAndAncestorTraverser();
                break;
            case Axis.DESCENDANTSFROMROOT:
                traverser = new DescendantFromRootTraverser();
                break;
            case Axis.DESCENDANTSORSELFFROMROOT:
                traverser = new DescendantOrSelfFromRootTraverser();
                break;
            case Axis.ROOT:
                traverser = new RootTraverser();
                break;
            case Axis.FILTEREDLIST:
                return null; // Don't want to throw an exception for this one.
            default:
                throw new DTMException(XMLMessages.createXMLMessage(XMLErrorResources.ER_UNKNOWN_AXIS_TYPE, new Object[] { Integer.toString(axis) })); //"Unknown axis traversal type: "+axis);
        }

        if (null == traverser)
            throw new DTMException(XMLMessages.createXMLMessage(XMLErrorResources.ER_AXIS_TRAVERSER_NOT_SUPPORTED, new Object[] { Axis.getNames(axis) }));
        // "Axis traverser not supported: "
        //                       + Axis.names[axis]);

        m_traversers[axis] = traverser;

        return traverser;
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class AncestorTraverser extends DTMAxisTraverser {

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node if this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {
            return getParent(current);
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {
            // Process using identities
            current = makeNodeIdentity(current);

            while (DTM.NULL != (current = m_parent.elementAt(current))) {
                if (m_exptype.elementAt(current) == expandedTypeID)
                    return makeNodeHandle(current);
            }

            return NULL;
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class AncestorOrSelfTraverser extends AncestorTraverser {

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  To see if
         * the self node should be processed, use this function.
         *
         * @param context The context node of this traversal.
         *
         * @return the first node in the traversal.
         */
        public int first(int context) {
            return context;
        }

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  To see if
         * the self node should be processed, use this function.  If the context
         * node does not match the expanded type ID, this function will return
         * false.
         *
         * @param context The context node of this traversal.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the first node in the traversal.
         */
        public int first(int context, int expandedTypeID) {
            return (getExpandedTypeID(context) == expandedTypeID) ? context : next(context, context, expandedTypeID);
        }
    }

    /**
     * Implements traversal of the Attribute access
     */
    private class AttributeTraverser extends DTMAxisTraverser {

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {
            return (context == current) ? getFirstAttribute(context) : getNextAttribute(current);
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {

            current = (context == current) ? getFirstAttribute(context) : getNextAttribute(current);

            do {
                if (getExpandedTypeID(current) == expandedTypeID)
                    return current;
            } while (DTM.NULL != (current = getNextAttribute(current)));

            return NULL;
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class ChildTraverser extends DTMAxisTraverser {

        /**
         * Get the next indexed node that matches the expanded type ID.  Before
         * calling this function, one should first call
         * {@link #isIndexed(int) isIndexed} to make sure that the index can
         * contain nodes that match the given expanded type ID.
         *
         * @param axisRoot The root identity of the axis.
         * @param nextPotential The node found must match or occur after this node.
         * @param expandedTypeID The expanded type ID for the request.
         *
         * @return The node ID or NULL if not found.
         */
        protected int getNextIndexed(int axisRoot, int nextPotential, int expandedTypeID) {

            int nsIndex = m_expandedNameTable.getNamespaceID(expandedTypeID);
            int lnIndex = m_expandedNameTable.getLocalNameID(expandedTypeID);

            for (;;) {
                int nextID = findElementFromIndex(nsIndex, lnIndex, nextPotential);

                if (NOTPROCESSED != nextID) {
                    int parentID = m_parent.elementAt(nextID);

                    // Is it a child?
                    if (parentID == axisRoot)
                        return nextID;

                    // If the parent occured before the subtree root, then
                    // we know it is past the child axis.
                    if (parentID < axisRoot)
                        return NULL;

                    // Otherwise, it could be a descendant below the subtree root
                    // children, or it could be after the subtree root.  So we have
                    // to climb up until the parent is less than the subtree root, in
                    // which case we return NULL, or until it is equal to the subtree
                    // root, in which case we continue to look.
                    do {
                        parentID = m_parent.elementAt(parentID);
                        if (parentID < axisRoot)
                            return NULL;
                    } while (parentID > axisRoot);

                    // System.out.println("Found node via index: "+first);
                    nextPotential = nextID + 1;
                    continue;
                }

                nextNode();

                if (!(m_nextsib.elementAt(axisRoot) == NOTPROCESSED))
                    break;
            }

            return DTM.NULL;
        }

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  So to traverse
         * an axis, the first function must be used to get the first node.
         *
         * <p>This method needs to be overloaded only by those axis that process
         * the self node. <\p>
         *
         * @param context The context node of this traversal. This is the point
         * that the traversal starts from.
         * @return the first node in the traversal.
         */
        public int first(int context) {
            return getFirstChild(context);
        }

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  So to traverse
         * an axis, the first function must be used to get the first node.
         *
         * <p>This method needs to be overloaded only by those axis that process
         * the self node. <\p>
         *
         * @param context The context node of this traversal. This is the point
         * of origin for the traversal -- its "root node" or starting point.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the first node in the traversal.
         */
        public int first(int context, int expandedTypeID) {
            if (true) {
                int identity = makeNodeIdentity(context);

                int firstMatch = getNextIndexed(identity, _firstch(identity), expandedTypeID);

                return makeNodeHandle(firstMatch);
            } else {
                // %REVIEW% Dead code. Eliminate?
                for (int current = _firstch(makeNodeIdentity(context)); DTM.NULL != current; current = _nextsib(current)) {
                    if (m_exptype.elementAt(current) == expandedTypeID)
                        return makeNodeHandle(current);
                }
                return NULL;
            }
        }

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {
            return getNextSibling(current);
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {
            // Process in Identifier space
            for (current = _nextsib(makeNodeIdentity(current)); DTM.NULL != current; current = _nextsib(current)) {
                if (m_exptype.elementAt(current) == expandedTypeID)
                    return makeNodeHandle(current);
            }

            return NULL;
        }
    }

    /**
     * Super class for derived classes that want a convenient way to access
     * the indexing mechanism.
     */
    private abstract class IndexedDTMAxisTraverser extends DTMAxisTraverser {

        /**
         * Tell if the indexing is on and the given expanded type ID matches
         * what is in the indexes.  Derived classes should call this before
         * calling {@link #getNextIndexed(int, int, int) getNextIndexed} method.
         *
         * @param expandedTypeID The expanded type ID being requested.
         *
         * @return true if it is OK to call the
         *         {@link #getNextIndexed(int, int, int) getNextIndexed} method.
         */
        protected final boolean isIndexed(int expandedTypeID) {
            return (m_indexing && ExpandedNameTable.ELEMENT == m_expandedNameTable.getType(expandedTypeID));
        }

        /**
         * Tell if a node is outside the axis being traversed.  This method must be
         * implemented by derived classes, and must be robust enough to handle any
         * node that occurs after the axis root.
         *
         * @param axisRoot The root identity of the axis.
         * @param identity The node in question.
         *
         * @return true if the given node falls outside the axis being traversed.
         */
        protected abstract boolean isAfterAxis(int axisRoot, int identity);

        /**
         * Tell if the axis has been fully processed to tell if a the wait for
         * an arriving node should terminate.  This method must be implemented
         * be a derived class.
         *
         * @param axisRoot The root identity of the axis.
         *
         * @return true if the axis has been fully processed.
         */
        protected abstract boolean axisHasBeenProcessed(int axisRoot);

        /**
         * Get the next indexed node that matches the expanded type ID.  Before
         * calling this function, one should first call
         * {@link #isIndexed(int) isIndexed} to make sure that the index can
         * contain nodes that match the given expanded type ID.
         *
         * @param axisRoot The root identity of the axis.
         * @param nextPotential The node found must match or occur after this node.
         * @param expandedTypeID The expanded type ID for the request.
         *
         * @return The node ID or NULL if not found.
         */
        protected int getNextIndexed(int axisRoot, int nextPotential, int expandedTypeID) {

            int nsIndex = m_expandedNameTable.getNamespaceID(expandedTypeID);
            int lnIndex = m_expandedNameTable.getLocalNameID(expandedTypeID);

            while (true) {
                int next = findElementFromIndex(nsIndex, lnIndex, nextPotential);

                if (NOTPROCESSED != next) {
                    if (isAfterAxis(axisRoot, next))
                        return NULL;

                    // System.out.println("Found node via index: "+first);
                    return next;
                } else if (axisHasBeenProcessed(axisRoot))
                    break;

                nextNode();
            }

            return DTM.NULL;
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class DescendantTraverser extends IndexedDTMAxisTraverser {
        /**
         * Get the first potential identity that can be returned.  This should
         * be overridded by classes that need to return the self node.
         *
         * @param identity The node identity of the root context of the traversal.
         *
         * @return The first potential node that can be in the traversal.
         */
        protected int getFirstPotential(int identity) {
            return identity + 1;
        }

        /**
         * Tell if the axis has been fully processed to tell if a the wait for
         * an arriving node should terminate.
         *
         * @param axisRoot The root identity of the axis.
         *
         * @return true if the axis has been fully processed.
         */
        protected boolean axisHasBeenProcessed(int axisRoot) {
            return !(m_nextsib.elementAt(axisRoot) == NOTPROCESSED);
        }

        /**
         * Get the subtree root identity from the handle that was passed in by
         * the caller.  Derived classes may override this to change the root
         * context of the traversal.
         *
         * @param handle handle to the root context.
         * @return identity of the root of the subtree.
         */
        protected int getSubtreeRoot(int handle) {
            return makeNodeIdentity(handle);
        }

        /**
         * Tell if this node identity is a descendant.  Assumes that
         * the node info for the element has already been obtained.
         *
         * %REVIEW% This is really parentFollowsRootInDocumentOrder ...
         * which fails if the parent starts after the root ends.
         * May be sufficient for this class's logic, but misleadingly named!
         *
         * @param subtreeRootIdentity The root context of the subtree in question.
         * @param identity The index number of the node in question.
         * @return true if the index is a descendant of _startNode.
         */
        protected boolean isDescendant(int subtreeRootIdentity, int identity) {
            return _parent(identity) >= subtreeRootIdentity;
        }

        /**
         * Tell if a node is outside the axis being traversed.  This method must be
         * implemented by derived classes, and must be robust enough to handle any
         * node that occurs after the axis root.
         *
         * @param axisRoot The root identity of the axis.
         * @param identity The node in question.
         *
         * @return true if the given node falls outside the axis being traversed.
         */
        protected boolean isAfterAxis(int axisRoot, int identity) {
            // %REVIEW% Is there *any* cheaper way to do this?
            // Yes. In ID space, compare to axisRoot's successor
            // (next-sib or ancestor's-next-sib). Probably shallower search.
            do {
                if (identity == axisRoot)
                    return false;
                identity = m_parent.elementAt(identity);
            } while (identity >= axisRoot);

            return true;
        }

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  So to traverse
         * an axis, the first function must be used to get the first node.
         *
         * <p>This method needs to be overloaded only by those axis that process
         * the self node. <\p>
         *
         * @param context The context node of this traversal. This is the point
         * of origin for the traversal -- its "root node" or starting point.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the first node in the traversal.
         */
        public int first(int context, int expandedTypeID) {

            if (isIndexed(expandedTypeID)) {
                int identity = getSubtreeRoot(context);
                int firstPotential = getFirstPotential(identity);

                return makeNodeHandle(getNextIndexed(identity, firstPotential, expandedTypeID));
            }

            return next(context, context, expandedTypeID);
        }

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {

            int subtreeRootIdent = getSubtreeRoot(context);

            for (current = makeNodeIdentity(current) + 1;; current++) {
                int type = _type(current); // may call nextNode()

                if (!isDescendant(subtreeRootIdent, current))
                    return NULL;

                if (ATTRIBUTE_NODE == type || NAMESPACE_NODE == type)
                    continue;

                return makeNodeHandle(current); // make handle.
            }
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {

            int subtreeRootIdent = getSubtreeRoot(context);

            current = makeNodeIdentity(current) + 1;

            if (isIndexed(expandedTypeID)) {
                return makeNodeHandle(getNextIndexed(subtreeRootIdent, current, expandedTypeID));
            }

            for (;; current++) {
                int exptype = _exptype(current); // may call nextNode()

                if (!isDescendant(subtreeRootIdent, current))
                    return NULL;

                if (exptype != expandedTypeID)
                    continue;

                return makeNodeHandle(current); // make handle.
            }
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class DescendantOrSelfTraverser extends DescendantTraverser {

        /**
         * Get the first potential identity that can be returned, which is the
         * axis context, in this case.
         *
         * @param identity The node identity of the root context of the traversal.
         *
         * @return The axis context.
         */
        protected int getFirstPotential(int identity) {
            return identity;
        }

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  To see if
         * the self node should be processed, use this function.
         *
         * @param context The context node of this traversal.
         *
         * @return the first node in the traversal.
         */
        public int first(int context) {
            return context;
        }
    }

    /**
     * Implements traversal of the entire subtree, including the root node.
     */
    private class AllFromNodeTraverser extends DescendantOrSelfTraverser {

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {

            int subtreeRootIdent = makeNodeIdentity(context);

            for (current = makeNodeIdentity(current) + 1;; current++) {
                // Trickological code: _exptype() has the side-effect of
                // running nextNode until the specified node has been loaded,
                // and thus can be used to ensure that incremental construction of
                // the DTM has gotten this far. Using it just for that side-effect
                // is quite a kluge...
                _exptype(current); // make sure it's here.

                if (!isDescendant(subtreeRootIdent, current))
                    return NULL;

                return makeNodeHandle(current); // make handle.
            }
        }
    }

    /**
     * Implements traversal of the following access, in document order.
     */
    private class FollowingTraverser extends DescendantTraverser {

        /**
         * Get the first of the following.
         *
         * @param context The context node of this traversal. This is the point
         * that the traversal starts from.
         * @return the first node in the traversal.
         */
        public int first(int context) {
            // Compute in ID space
            context = makeNodeIdentity(context);

            int first;
            int type = _type(context);

            if ((DTM.ATTRIBUTE_NODE == type) || (DTM.NAMESPACE_NODE == type)) {
                context = _parent(context);
                first = _firstch(context);

                if (NULL != first)
                    return makeNodeHandle(first);
            }

            do {
                first = _nextsib(context);

                if (NULL == first)
                    context = _parent(context);
            } while (NULL == first && NULL != context);

            return makeNodeHandle(first);
        }

        /**
         * Get the first of the following.
         *
         * @param context The context node of this traversal. This is the point
         * of origin for the traversal -- its "root node" or starting point.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the first node in the traversal.
         */
        public int first(int context, int expandedTypeID) {
            // %REVIEW% This looks like it might want shift into identity space
            // to avoid repeated conversion in the individual functions
            int first;
            int type = getNodeType(context);

            if ((DTM.ATTRIBUTE_NODE == type) || (DTM.NAMESPACE_NODE == type)) {
                context = getParent(context);
                first = getFirstChild(context);

                if (NULL != first) {
                    if (getExpandedTypeID(first) == expandedTypeID)
                        return first;
                    else
                        return next(context, first, expandedTypeID);
                }
            }

            do {
                first = getNextSibling(context);

                if (NULL == first)
                    context = getParent(context);
                else {
                    if (getExpandedTypeID(first) == expandedTypeID)
                        return first;
                    else
                        return next(context, first, expandedTypeID);
                }
            } while (NULL == first && NULL != context);

            return first;
        }

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {
            // Compute in identity space
            current = makeNodeIdentity(current);

            while (true) {
                current++; // Only works on IDs, not handles.

                // %REVIEW% Are we using handles or indexes?
                int type = _type(current); // may call nextNode()

                if (NULL == type)
                    return NULL;

                if (ATTRIBUTE_NODE == type || NAMESPACE_NODE == type)
                    continue;

                return makeNodeHandle(current); // make handle.
            }
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {
            // Compute in ID space
            current = makeNodeIdentity(current);

            while (true) {
                current++;

                int etype = _exptype(current); // may call nextNode()

                if (NULL == etype)
                    return NULL;

                if (etype != expandedTypeID)
                    continue;

                return makeNodeHandle(current); // make handle.
            }
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class FollowingSiblingTraverser extends DTMAxisTraverser {

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {
            return getNextSibling(current);
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {

            while (DTM.NULL != (current = getNextSibling(current))) {
                if (getExpandedTypeID(current) == expandedTypeID)
                    return current;
            }

            return NULL;
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class NamespaceDeclsTraverser extends DTMAxisTraverser {

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {

            return (context == current) ? getFirstNamespaceNode(context, false) : getNextNamespaceNode(context, current, false);
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {

            current = (context == current) ? getFirstNamespaceNode(context, false) : getNextNamespaceNode(context, current, false);

            do {
                if (getExpandedTypeID(current) == expandedTypeID)
                    return current;
            } while (DTM.NULL != (current = getNextNamespaceNode(context, current, false)));

            return NULL;
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class NamespaceTraverser extends DTMAxisTraverser {

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {

            return (context == current) ? getFirstNamespaceNode(context, true) : getNextNamespaceNode(context, current, true);
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {

            current = (context == current) ? getFirstNamespaceNode(context, true) : getNextNamespaceNode(context, current, true);

            do {
                if (getExpandedTypeID(current) == expandedTypeID)
                    return current;
            } while (DTM.NULL != (current = getNextNamespaceNode(context, current, true)));

            return NULL;
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class ParentTraverser extends DTMAxisTraverser {
        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  So to traverse
         * an axis, the first function must be used to get the first node.
         *
         * <p>This method needs to be overloaded only by those axis that process
         * the self node. <\p>
         *
         * @param context The context node of this traversal. This is the point
         * that the traversal starts from.
         * @return the first node in the traversal.
         */
        public int first(int context) {
            return getParent(context);
        }

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  So to traverse
         * an axis, the first function must be used to get the first node.
         *
         * <p>This method needs to be overloaded only by those axis that process
         * the self node. <\p>
         *
         * @param context The context node of this traversal. This is the point
         * of origin for the traversal -- its "root node" or starting point.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the first node in the traversal.
         */
        public int first(int current, int expandedTypeID) {
            // Compute in ID space
            current = makeNodeIdentity(current);

            while (NULL != (current = m_parent.elementAt(current))) {
                if (m_exptype.elementAt(current) == expandedTypeID)
                    return makeNodeHandle(current);
            }

            return NULL;
        }

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {

            return NULL;
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {

            return NULL;
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class PrecedingTraverser extends DTMAxisTraverser {

        /**
         * Tell if the current identity is an ancestor of the context identity.
         * This is an expensive operation, made worse by the stateless traversal.
         * But the preceding axis is used fairly infrequently.
         *
         * @param contextIdent The context node of the axis traversal.
         * @param currentIdent The node in question.
         * @return true if the currentIdent node is an ancestor of contextIdent.
         */
        protected boolean isAncestor(int contextIdent, int currentIdent) {
            // %REVIEW% See comments in IsAfterAxis; using the "successor" of
            // contextIdent is probably more efficient.
            for (contextIdent = m_parent.elementAt(contextIdent); DTM.NULL != contextIdent; contextIdent = m_parent.elementAt(contextIdent)) {
                if (contextIdent == currentIdent)
                    return true;
            }

            return false;
        }

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {
            // compute in ID space
            int subtreeRootIdent = makeNodeIdentity(context);

            for (current = makeNodeIdentity(current) - 1; current >= 0; current--) {
                short type = _type(current);

                if (ATTRIBUTE_NODE == type || NAMESPACE_NODE == type || isAncestor(subtreeRootIdent, current))
                    continue;

                return makeNodeHandle(current); // make handle.
            }

            return NULL;
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {
            // Compute in ID space
            int subtreeRootIdent = makeNodeIdentity(context);

            for (current = makeNodeIdentity(current) - 1; current >= 0; current--) {
                int exptype = m_exptype.elementAt(current);

                if (exptype != expandedTypeID || isAncestor(subtreeRootIdent, current))
                    continue;

                return makeNodeHandle(current); // make handle.
            }

            return NULL;
        }
    }

    /**
     * Implements traversal of the Ancestor and the Preceding axis,
     * in reverse document order.
     */
    private class PrecedingAndAncestorTraverser extends DTMAxisTraverser {

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {
            // Compute in ID space
            int subtreeRootIdent = makeNodeIdentity(context);

            for (current = makeNodeIdentity(current) - 1; current >= 0; current--) {
                short type = _type(current);

                if (ATTRIBUTE_NODE == type || NAMESPACE_NODE == type)
                    continue;

                return makeNodeHandle(current); // make handle.
            }

            return NULL;
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {
            // Compute in ID space
            int subtreeRootIdent = makeNodeIdentity(context);

            for (current = makeNodeIdentity(current) - 1; current >= 0; current--) {
                int exptype = m_exptype.elementAt(current);

                if (exptype != expandedTypeID)
                    continue;

                return makeNodeHandle(current); // make handle.
            }

            return NULL;
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class PrecedingSiblingTraverser extends DTMAxisTraverser {

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {
            return getPreviousSibling(current);
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {

            while (DTM.NULL != (current = getPreviousSibling(current))) {
                if (getExpandedTypeID(current) == expandedTypeID)
                    return current;
            }

            return NULL;
        }
    }

    /**
     * Implements traversal of the Self axis.
     */
    private class SelfTraverser extends DTMAxisTraverser {

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  To see if
         * the self node should be processed, use this function.
         *
         * @param context The context node of this traversal.
         *
         * @return the first node in the traversal.
         */
        public int first(int context) {
            return context;
        }

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  To see if
         * the self node should be processed, use this function.  If the context
         * node does not match the expanded type ID, this function will return
         * false.
         *
         * @param context The context node of this traversal.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the first node in the traversal.
         */
        public int first(int context, int expandedTypeID) {
            return (getExpandedTypeID(context) == expandedTypeID) ? context : NULL;
        }

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return Always return NULL for this axis.
         */
        public int next(int context, int current) {
            return NULL;
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {
            return NULL;
        }
    }

    /**
     * Implements traversal of the Ancestor access, in reverse document order.
     */
    private class AllFromRootTraverser extends AllFromNodeTraverser {

        /**
         * Return the root.
         *
         * @param context The context node of this traversal.
         *
         * @return the first node in the traversal.
         */
        public int first(int context) {
            return getDocumentRoot(context);
        }

        /**
         * Return the root if it matches the expanded type ID.
         *
         * @param context The context node of this traversal.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the first node in the traversal.
         */
        public int first(int context, int expandedTypeID) {
            return (getExpandedTypeID(getDocumentRoot(context)) == expandedTypeID) ? context : next(context, context, expandedTypeID);
        }

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current) {
            // Compute in ID space
            int subtreeRootIdent = makeNodeIdentity(context);

            for (current = makeNodeIdentity(current) + 1;; current++) {
                // Kluge test: Just make sure +1 yielded a real node
                int type = _type(current); // may call nextNode()
                if (type == NULL)
                    return NULL;

                return makeNodeHandle(current); // make handle.
            }
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {
            // Compute in ID space
            int subtreeRootIdent = makeNodeIdentity(context);

            for (current = makeNodeIdentity(current) + 1;; current++) {
                int exptype = _exptype(current); // may call nextNode()

                if (exptype == NULL)
                    return NULL;

                if (exptype != expandedTypeID)
                    continue;

                return makeNodeHandle(current); // make handle.
            }
        }
    }

    /**
     * Implements traversal of the Self axis.
     */
    private class RootTraverser extends AllFromRootTraverser {
        /**
         * Return the root if it matches the expanded type ID,
         * else return null (nothing found)
         *
         * @param context The context node of this traversal.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the first node in the traversal.
         */
        public int first(int context, int expandedTypeID) {
            int root = getDocumentRoot(context);
            return (getExpandedTypeID(root) == expandedTypeID) ? root : NULL;
        }

        /**
         * Traverse to the next node after the current node.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         *
         * @return Always return NULL for this axis.
         */
        public int next(int context, int current) {
            return NULL;
        }

        /**
         * Traverse to the next node after the current node that is matched
         * by the expanded type ID.
         *
         * @param context The context node of this iteration.
         * @param current The current node of the iteration.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the next node in the iteration, or DTM.NULL.
         */
        public int next(int context, int current, int expandedTypeID) {
            return NULL;
        }
    }

    /**
     * A non-xpath axis, returns all nodes that aren't namespaces or attributes,
     * from and including the root.
     */
    private class DescendantOrSelfFromRootTraverser extends DescendantTraverser {

        /**
         * Get the first potential identity that can be returned, which is the axis
         * root context in this case.
         *
         * @param identity The node identity of the root context of the traversal.
         *
         * @return The identity argument.
         */
        protected int getFirstPotential(int identity) {
            return identity;
        }

        /**
         * Get the first potential identity that can be returned.
         * @param handle handle to the root context.
         * @return identity of the root of the subtree.
         */
        protected int getSubtreeRoot(int handle) {
            // %REVIEW% Shouldn't this always be 0?
            return makeNodeIdentity(getDocument());
        }

        /**
         * Return the root.
         *
         * @param context The context node of this traversal.
         *
         * @return the first node in the traversal.
         */
        public int first(int context) {
            return getDocumentRoot(context);
        }

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  So to traverse
         * an axis, the first function must be used to get the first node.
         *
         * <p>This method needs to be overloaded only by those axis that process
         * the self node. <\p>
         *
         * @param context The context node of this traversal. This is the point
         * of origin for the traversal -- its "root node" or starting point.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the first node in the traversal.
         */
        public int first(int context, int expandedTypeID) {
            if (isIndexed(expandedTypeID)) {
                int identity = 0;
                int firstPotential = getFirstPotential(identity);

                return makeNodeHandle(getNextIndexed(identity, firstPotential, expandedTypeID));
            }

            int root = first(context);
            return next(root, root, expandedTypeID);
        }
    }

    /**
     * A non-xpath axis, returns all nodes that aren't namespaces or attributes,
     * from but not including the root.
     */
    private class DescendantFromRootTraverser extends DescendantTraverser {

        /**
         * Get the first potential identity that can be returned, which is the axis
         * root context in this case.
         *
         * @param identity The node identity of the root context of the traversal.
         *
         * @return The identity argument.
         */
        protected int getFirstPotential(int identity) {
            return _firstch(0);
        }

        /**
         * Get the first potential identity that can be returned.
         * @param handle handle to the root context.
         * @return identity of the root of the subtree.
         */
        protected int getSubtreeRoot(int handle) {
            return 0;
        }

        /**
         * Return the root.
         *
         * @param context The context node of this traversal.
         *
         * @return the first node in the traversal.
         */
        public int first(int context) {
            return makeNodeHandle(_firstch(0));
        }

        /**
         * By the nature of the stateless traversal, the context node can not be
         * returned or the iteration will go into an infinate loop.  So to traverse
         * an axis, the first function must be used to get the first node.
         *
         * <p>This method needs to be overloaded only by those axis that process
         * the self node. <\p>
         *
         * @param context The context node of this traversal. This is the point
         * of origin for the traversal -- its "root node" or starting point.
         * @param expandedTypeID The expanded type ID that must match.
         *
         * @return the first node in the traversal.
         */
        public int first(int context, int expandedTypeID) {
            if (isIndexed(expandedTypeID)) {
                int identity = 0;
                int firstPotential = getFirstPotential(identity);

                return makeNodeHandle(getNextIndexed(identity, firstPotential, expandedTypeID));
            }

            int root = getDocumentRoot(context);
            return next(root, root, expandedTypeID);
        }

    }

}
